package q801_minSwap;

import java.util.Arrays;

public class Solution_1 {
    /*
    题目说给定的输入是有效的，那么就意味着不会存在  不能使 A、B 数组严格递增的交换方法，即不存在下列的数组情况
    A = {4 3}
    B = {1 2}
    上述数组怎么交换都是不满足条件的，因此这种情况是不会出现的

    A = {0 2 7 8}
    B = {1 5 4 9}
             ↑
             i
    对于位置 i ，必定 满足以下两种情况 之一 或 同时满足：
    1、A[i] > A[i - 1] && B[i] > B[i - 1]
    2、A[i] > B[i - 1] && B[i] > A[i - 1]
    第一种情况很好理解
    第二种的话，就是如果至少存在 A、B 一边不是严格递增的，这表示需要进行交换，
    而能够交换的前提，就是交换后的值必定满足递增，即如果是 A[i] 和 B[i] 交换，那么 B[i] 必须大于 A[i - 1]，同理新的 A[i] > B[i - 1]，才能在交换后递增

    当只满足 A[i] > A[i - 1] && B[i] > B[i - 1]，那么我们可以有以下选择：
        1、i 交换，那么 i - 1 必须交换
        2、i 不交换，那么 i - 1 必须不交换
    当只满足 A[i] > B[i - 1] && B[i] > A[i - 1]，那么我们可以有以下选择：
        1、i 交换，那么 i - 1 必须不交换
        2、i 不交换，那么 i - 1 必须交换
    当同时满足两个条件，即 A[i] > A[i - 1] && B[i] > B[i - 1]，同时 A[i] > B[i - 1] && B[i] > A[i - 1]，那么我们可以有这么几种情况：
        1、 i 交换，那么 i - 1 可以选择交换或不交换，选择最优情况
        2、 i 不交换，那么 i - 1 同样可以选择 交换 或 不交换，选择最优情况

    我们需要对交换 i 和 交换 i - 1 进行判断哪种交换方式才是最优，
    那么我们就需要使用 一个 二维数组 或 两个 一维数组   ：  一个记录交换 i 的情况，一个记录交换 i - 1 的情况
     */
    public int minSwap(int[] A, int[] B) {
        int len = A.length;
        // 不交换 i 的情况
        int[] keep = new int[len];
        // 交换 i 的情况
        int[] swap = new int[len];
        Arrays.fill(keep, Integer.MAX_VALUE);
        Arrays.fill(swap, Integer.MAX_VALUE);
        // 初始条件，第 0 个位置不交换，次数为 0，第 0 个位置交换，次数为 1
        keep[0] = 0;
        swap[0] = 1;
        for(int i = 1; i < len; i++){
            /*
            如果满足两种情况
            i 交换的情况下，可以有 i - 1 不交换 和 i - 1 交换，选择最优情况
            i 不交换的情况下，可以有 i - 1 交换和 i - 1 不交换，选择最优情况
            */
            if((A[i] > A[i - 1] && B[i] > B[i - 1]) && (A[i] > B[i - 1] && B[i] > A[i - 1])){
                // i 不交换
                keep[i] = Math.min(keep[i - 1], swap[i - 1]);
                // i 交换
                swap[i] = Math.min(swap[i - 1], keep[i - 1]) + 1;
                continue;
            }

            if(A[i] > A[i - 1] && B[i] > B[i - 1]){
                // i 不交换
                keep[i] = keep[i - 1];
                // i 交换，那么意味着 i - 1 也交换
                swap[i] = swap[i - 1] + 1;
            }

            if(A[i] > B[i - 1] && B[i] > A[i - 1]){
                // i 不交换，那么就是交换 i - 1
                keep[i] = swap[i - 1];
                // i 交换，那么就是 i - 1 不交换
                swap[i] = keep[i - 1] + 1;
            }
        }
        return Math.min(keep[len - 1], swap[len - 1]);
    }

}
